class Solution {
    public:
        vector<vector<string>> partition(string s) {
            int n = s.size();
            vector<vector<bool>> dp(n, vector<bool>(n,false));
            vector<vector<string>> ans;
            for (int i = 0; i < n; i++) {
                for (int j = i; j >= 0; j--) {
                    if (s[i] == s[j] && (i - j < 2 || dp[i - 1][j + 1])) {
                        dp[i][j] = true;
                    }
                    //  cout << dp[i][j] <<' ';
                }
                // cout << endl;
            }
            vector<string> vstr;
            auto dfs = [&](auto&& dfs,int pos) {
                if (pos == n) {
                    ans.push_back(vstr);
                    return;
                }
                for (int i = pos; i < n; i++) {
                    if (dp[i][pos] == true) {
                        vstr.push_back(s.substr(pos, i - pos + 1));
                        dfs(dfs,i + 1);
                        vstr.pop_back();
                    }
                }
                return;
            };
            dfs(dfs,0);
            return ans;
        }
    };